A general branch-and-bound framework for global multiobjective optimization

Abstract: We develop a general framework for branch-and-bound methods in multiobjective optimization. Our focus is on natural generalizations of notions and techniques from the single objective case. In particular, after the notions of upper and lower bounds on the globally optimal value from the single objective case have been transferred to upper and lower bounding sets on the set of nondominated points for multiobjective programs, we discuss several possibilities for discarding tests. They compare local upper bounds of the provisional nondominated sets with relaxations of partial upper image sets, where the latter can stem from ideal point estimates, from convex relaxations, or from relaxations by a reformulation-linearization technique. The discussion of approximation properties of the provisional nondominated set leads to the suggestion for a natural selection rule along with a natural termination criterion. Finally we discuss some issues which do not occur in the single objective case and which impede some desirable convergence properties, thus also motivating a natural generalization of the convergence concept.

This is joint work with Gabriele Eichfelder, Peter Kirst, and Laura Meng.

optimization and control

Audience: researchers in the topic

Variational Analysis and Optimisation Webinar

Series comments: Register on www.mocao.org/va-webinar/ to receive information about the zoom connection.